package com.frx.datastruct.chapterthree;

/**
 * @author ：frx
 * @date ：Created in 2019/2/1 22:44
 * @description： 循环队列的实现
 * 定义两个指针 front,tail front==tail时队列为空， (tail + 1)%c == front 时队列为满
 * @modified By：
 * @version: ToDO
 */
public class LoopQueue<E> implements Queue<E>{

    /** 使用自己维护的数组 */
    private E[] data;
    /** 定义头尾指针 */
    private int front,tail;
    /** 大小 */
    private int size;

    public LoopQueue(int capacity){
        data = (E[])new Object[capacity +1];
        size = 0;
        front = 0;
        tail = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length -1;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /** 队列入队操作 */
    @Override
    public void enqueue(E e) {
        //判断队列是否是满的，是的话进行扩容
        if((tail +1)%data.length == front){
            resize(getCapacity()*2);

        }
        data[tail] = e;
        tail = (tail + 1)%data.length;
        size++;

    }

    /** 扩容的操作 */
    public void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity + 1];
        for(int i = 0;i<size;i++){
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }
    /** 循环队列的出队操作 */
    @Override
    public E dequeue() {
        if(isEmpty()){
            throw  new IllegalArgumentException("Cannot dequeue from an empty queue!");
        }
        //出队首元素
        E ret = data[front];
        // 为了更好地进行垃圾回收
        data[front] = null;
        front = (front + 1)%data.length;
        size--;
        //节省空间，进行缩容操作
        if(size == getCapacity()/4 && getCapacity()/2!=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    /** 返回队首元素的方法 */
    @Override
    public E getFront() {
        if(isEmpty()){
            throw  new IllegalArgumentException("Queue is empty !");
        }
        return data[front];
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d,capacity = %d\n",size,getCapacity()));
        res.append("front [");
        for(int i = front;i!=tail;i=(i+1)%data.length){
            res.append(data[i]);
            //判断是不是队尾元素
            if((i+1)%data.length !=tail){
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

}
